package com.wfm.leetcode.editor.cn;

import com.wfm.alg.P线段树;
import com.wfm.alg.P线段树.SegTreeDynamic;
import com.wfm.alg.P线段树.SegTreeDynamic.Node;
import org.junit.Test;

public class PSeven15Range模块 {

    //leetcode submit region begin(Prohibit modification and deletion)
    class RangeModule {


        public RangeModule() {
        }

        public void addRange(int left, int right) {
            updateSetSum(root, 0, N, left, right - 1, 1);
        }

        public boolean queryRange(int left, int right) {
            int i = querySetSum(root, 0, N, left, right - 1);
            if (i != (right - left)) {
                return false;
            } else {
                return true;
            }
        }

        public void removeRange(int left, int right) {
            updateSetSum(root, 0, N, left, right - 1, 0);
        }

        public class Node {

            Node left, right;
            int val, add;
        }

        public int N = (int) 1e9;
        public Node root = new Node();

        public void updateSetSum(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val = (end - start + 1) * val;
                node.add = val;
                return;
            }
            int mid = (start + end) >> 1;
            pushDown2(node, mid - start + 1, end - mid);
            if (r <= mid) {
                updateSetSum(node.left, start, mid, l, r, val);
            } else if (l > mid) {
                updateSetSum(node.right, mid + 1, end, l, r, val);
            } else {
                updateSetSum(node.left, start, mid, l, mid, val);
                updateSetSum(node.right, mid + 1, end, mid + 1, r, val);
            }
            node.val = node.left.val + node.right.val;
        }

        // 在区间 [start, end] 中查询区间 [l, r] 的结果，即 [l ,r] 保持不变
        public int querySetSum(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) {
                return node.val;
            }
            int mid = (start + end) >> 1, ans = 0;
            pushDown2(node, mid - start + 1, end - mid);
            if (r <= mid) {
                ans = querySetSum(node.left, start, mid, l, r);
            } else if (l > mid) {
                ans = querySetSum(node.right, mid + 1, end, l, r);
            } else {
                ans = querySetSum(node.left, start, mid, l, mid) +
                        querySetSum(node.right, mid + 1, end, mid + 1, r);
            }
            return ans;
        }

        private void pushDown2(Node node, int leftNum, int rightNum) {
            // 动态开点 如果节点没有左右子节点，先开个没有值的节点
            if (node.left == null) {
                node.left = new Node();
            }
            if (node.right == null) {
                node.right = new Node();
            }
            if (node.add == 0) {
                return;
            }
            node.left.val = node.add * leftNum;
            node.right.val = node.add * rightNum;

            node.left.add = node.add;
            node.right.add = node.add;
            node.add = 0;
        }
    }

    /**
     * Your RangeModule object will be instantiated and called as such:
     * RangeModule obj = new RangeModule();
     * obj.addRange(left,right);
     * boolean param_2 = obj.queryRange(left,right);
     * obj.removeRange(left,right);
     */
//leetcode submit region end(Prohibit modification and deletion)
    public static void main(String[] args) {
//        RangeModule solution = new PSeven15Range模块().new RangeModule();
//        solution.addRange(5, 7);
//        solution.queryRange(2, 7);
//        System.out.println(solution.queryRange(10, 14));
//        System.out.println(solution.queryRange(13, 15));
//        System.out.println(solution.queryRange(16, 17));

        P线段树.SegTreeDynamic tree = new P线段树.SegTreeDynamic();
        tree.updateSetSum(tree.root, 0, tree.N, 5, 7 - 1, 1);
        pt(tree,10);
        System.out.println(tree.querySetSum(tree.root, 0, tree.N, 2, 7 - 1));

        tree.updateSetSum(tree.root, 0, tree.N, 6, 9 - 1, 1);
        pt(tree,10);
        System.out.println(tree.querySetSum(tree.root, 0, tree.N, 2, 9 - 1));

        tree.updateSetSum(tree.root, 0, tree.N, 2, 7 - 1, 1);
        pt(tree,10);
        System.out.println(tree.querySetSum(tree.root, 0, tree.N, 2, 9 - 1));

        tree.updateSetSum(tree.root, 0, tree.N, 3, 10 - 1, 0);
        pt(tree,10);
        System.out.println(tree.querySetSum(tree.root, 0, tree.N, 2, 10 - 1));

        tree.updateSetSum(tree.root, 0, tree.N, 1, 8 - 1, 0);
        pt(tree,10);
        System.out.println(tree.querySetSum(tree.root, 0, tree.N, 1, 10 - 1));

        tree.updateSetSum(tree.root, 0, tree.N, 1, 10 - 1, 0);
        pt(tree,10);
        System.out.println(tree.querySetSum(tree.root, 0, tree.N, 1, 10 - 1));

        System.out.println("=========");
        System.out.println(tree.querySetSum(tree.root, 0, tree.N, 4, 7 - 1));
    }
    public static void pt(P线段树.SegTreeDynamic tree,int n ){
        for (int i = 0; i <= n; i++) {
            System.out.println("====>"+tree.querySumMax(tree.root, 0, tree.N, i,i));
        }
    }

    public static void pt1(NumArray tree,int n ){
        for (int i = 0; i <= n; i++) {
            System.out.println("====>"+tree.query(tree.root, 0, tree.N, i,i));
        }
    }
    @Test
    public void test(){
        NumArray numArray = new NumArray();
        numArray.update(numArray.root, 0, numArray.N, 5, 7 - 1, 1);
        pt1(numArray,10);
        System.out.println(numArray.query(numArray.root, 0, numArray.N, 2, 7 - 1));

        numArray.update(numArray.root, 0, numArray.N, 6, 9 - 1, 1);
        pt1(numArray,10);
        System.out.println(numArray.query(numArray.root, 0, numArray.N, 2, 9 - 1));

        numArray.update(numArray.root, 0, numArray.N, 2, 7 - 1, 1);
        pt1(numArray,10);
        System.out.println(numArray.query(numArray.root, 0, numArray.N, 2, 9 - 1));

        numArray.update(numArray.root, 0, numArray.N, 3, 10 - 1, 0);
        pt1(numArray,10);
        System.out.println(numArray.query(numArray.root, 0, numArray.N, 2, 10 - 1));

        numArray.update(numArray.root, 0, numArray.N, 1, 8 - 1, 0);
        pt1(numArray,10);
        System.out.println(numArray.query(numArray.root, 0, numArray.N, 1, 10 - 1));

        numArray.update(numArray.root, 0, numArray.N, 1, 10 - 1, 0);
        pt1(numArray,10);
        System.out.println(numArray.query(numArray.root, 0, numArray.N, 4, 10 - 1));

        System.out.println("=========");
        System.out.println(numArray.query(numArray.root, 0, numArray.N, 4, 7 - 1));
    }

    class NumArray {
        class Node {
            // 左右孩子节点
            Node left, right;
            // 当前节点值，以及懒惰标记的值
            int val, add;
        }
        private int N=(int) 1e9;
        private Node root = new Node();
        public void update(Node node, int start, int end, int l, int r, int val) {
            if (l <= start && end <= r) {
                node.val = (end - start + 1) * val;
                node.add = val;
                return ;
            }
            int mid = (start + end) >> 1;
            pushDown(node, mid - start + 1, end - mid);
            if (l <= mid) update(node.left, start, mid, l, r, val);
            if (r > mid) update(node.right, mid + 1, end, l, r, val);
            pushUp(node);
        }
        public int query(Node node, int start, int end, int l, int r) {
            if (l <= start && end <= r) return node.val;
            int mid = (start + end) >> 1, ans = 0;
            pushDown(node, mid - start + 1, end - mid);
            if (l <= mid) ans += query(node.left, start, mid, l, r);
            if (r > mid) ans += query(node.right, mid + 1, end, l, r);
            return ans;
        }
        private void pushUp(Node node) {
            node.val = node.left.val + node.right.val;
        }
        private void pushDown(Node node, int leftNum, int rightNum) {
            if (node.left == null) node.left = new Node();
            if (node.right == null) node.right = new Node();
            if (node.add == 0) return ;
            node.left.val = node.add * leftNum;
            node.right.val = node.add * rightNum;
            node.left.add = node.add;
            node.right.add = node.add;
            node.add = 0;
        }
    }
}